package Leetcode;

import java.util.Map;

import base.ListNode;

/**
 * 给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。
 * k是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
 */
public class 力扣25_K个一组翻转链表 {
    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        ListNode listNode = reverseKGroup(a, 3);
        System.out.println();
    }

    /**
     * 递归得到结果
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        ListNode end = head;
        for (int i = 1; i < k; i++) {
            if (end.next == null) {
                return head;
            }
            end = end.next;
        }
        ListNode nextHead = end.next;

        Map<String, ListNode> pair = reverse(head, end);
        ListNode newStart = pair.get("end");
        ListNode newEnd = pair.get("tail");
        newEnd.next = reverseKGroup(nextHead, k);
        return newStart;
    }

    /**
     * 反转链表
     */
    private static Map<String, ListNode> reverse(ListNode start, ListNode end) {
        ListNode tail = start;

        ListNode pre = null;
        while (start != null) {
            ListNode next = start.next;
            start.next = pre;
            pre = start;
            if (start == end) {
                break;
            }
            start = next;
        }

        return Map.of("end", end, "tail", tail);
    }
}
